/***************************************************************************************************
  *Copyright(C),2010-2016,Sumscope
  *FileName	:  StringIntHashMap.cpp
  *Author	:  scofined.qi
  *Version	:  1.0
  *Date		:  2020/05/22
  *Desc		:  //用于主要说明此程序文件完成的主要功能
  *Relation :  
  *Others	:  //其他内容说明
  *Function :  //主要函数列表，每条记录应包含函数名及功能简要说明
  *History	:  //修改历史记录列表，每条修改记录应包含修改日期、修改者及修改内容简介
***************************************************************************************************/
#include "StringIntHashMap.h"
#include "KeyHashMap.h"
#include <list>
#include <unordered_map>
#include <map>
#include <string>

#define BASSERT //
#define BLOGINFO //

namespace qb{
	namespace base{
		namespace util{
			bool GetUpperExp2(int& num, unsigned short& bitcount)
			{
				for (int i = 0; i <= 31; i++)
				{
					if (num <= (1 << i))
					{
						bitcount = i;
						num = 1 << i;
						return true;
					}
				}
				return false;
			}
			bool GetExactExp2(int num, int& bitcount)
			{
				for (int i = 0; i <= 31; i++)
				{
					if (num == (1 << i))
					{
						bitcount = i;
						return true;
					}
				}
				return false;
			}

			inline unsigned int InlineMurMurHash(const void *key, int len)
			{
				const unsigned int m = 0x5bd1e995;
				const int r = 24;
				const int seed = 97;
				unsigned int h = seed ^ len;
				// Mix 4 bytes at a time into the hash
				const unsigned char *data = (const unsigned char *)key;
				while (len >= 4)
				{
					unsigned int k = *(unsigned int *)data;
					k *= m;
					k ^= k >> r;
					k *= m;
					h *= m;
					h ^= k;
					data += 4;
					len -= 4;
				}
				// Handle the last few bytes of the input array
				switch (len)
				{
				case 3: h ^= data[2] << 16;
				case 2: h ^= data[1] << 8;
				case 1: h ^= data[0];
					h *= m;
				};
				// Do a few final mixes of the hash to ensure the last few
				// bytes are well-incorporated.
				h ^= h >> 13;
				h *= m;
				h ^= h >> 15;
				return h;
			}
		}
		
		namespace test{
			class KeyRecordIdHashMap{
				struct ColumnKey{
					const char*	ptr;			// 在Alloc中分配,在~Entry中释放
					int			rid;			//
					int			bytes;			// ptr的长度,有效,不包括结尾0
					ColumnKey() :ptr(0), rid(-1), bytes(0){}
					inline bool operator==(const ColumnKey& key)const
					{
						if (bytes == key.bytes && bytes > 0 && memcmp(ptr, key.ptr, bytes) == 0)
							return true;
						return false;
					}
					inline unsigned int GetHash()const
					{
						return qb::base::GetFastHash(ptr, bytes, 0);
					}
					inline void Reset(){ if (ptr)delete[] ptr; ptr = nullptr; bytes = 0; rid = 0; }
				};
				struct Entry{
					Entry*			hashprev;			// 哈西插槽的双链表的后一个
					Entry*			hashnext;			// 哈西插槽的双链表的前一个
					ColumnKey		key;				// 用于标志
					Entry() :hashnext(0), hashprev(0){}
					~Entry(){ key.Reset(); }
				};
				class ObjectPool{
					typedef Entry Type;
					std::list<Type*>		m_unused;
					int				m_capcity;		// 默认-1,表示全部缓存
					int				m_allocated;
				public:
					ObjectPool(int capcity = -1) :m_capcity(capcity), m_allocated(0){}
					~ObjectPool(){
						std::list<Type*>::iterator it = m_unused.begin();
						for (; it != m_unused.end(); ++it)
						{
							delete *it;
						}
					}
					int GetCount()const{ return m_unused.size(); }
					int GetCapcity()const{ return m_capcity; }
					int GetAllocated()const{ return m_allocated; }
					void SetCapcity(int capcity){ m_capcity = capcity; }
					Type* Alloc(){
						Type* type = 0;
						if (!m_unused.empty())
						{
							type = m_unused.front();
							m_unused.pop_front();
						}
						else
							type = new Type();
						m_allocated++;
						return type;
					}
					void Free(Type* t){
						BASSERT(t);
						m_allocated--;
						if (m_capcity > 0 && (int)m_unused.size() >= m_capcity)
						{
							delete t;
						}
						else
							m_unused.push_back(t);
					}
				};
				typedef int kDataType;
				typedef qb::base::KeyHashMap<Entry, ColumnKey> ColumnKeyHashMap;
				kDataType			m_data_type;		//
				int					m_key_bytes;		//
				int					m_mem_bytes;		// Entry.key.ptr所占据的内存
				ColumnKeyHashMap	m_hashmap;			// 
				ObjectPool			m_entry_pool;		//
			public:
				KeyRecordIdHashMap(kDataType type, int bytes) :m_data_type(type), m_key_bytes(bytes),
					m_mem_bytes(0){
					m_hashmap.Build(qb::base::GetHashPrimeLargerThan(160));
				}
				~KeyRecordIdHashMap()
				{
					int length = m_hashmap.GetLength();
					for (int i = 0; i < length; i++)
					{
						Entry* head = m_hashmap.GetHead(i);
						while (head)
						{
							Entry* temp = head;
							head = head->hashnext;
							delete temp;
						}
					}
					m_hashmap.Clear();
				}
				int GetMemoryBytes()const{
					int bytes = m_hashmap.GetBytes() + sizeof(*this);
					bytes += (m_entry_pool.GetAllocated() + m_entry_pool.GetCount())*(sizeof(Entry));
					bytes += m_mem_bytes;
					return bytes;
				}
				bool emplace(const char* key, int rid)
				{

				}
				int find(const void* key)
				{
					if (key == nullptr)return -1;
					ColumnKey ckey;
					ckey.ptr = (const char*)key;
					ckey.bytes = strlen(ckey.ptr);
					ckey.rid = -1;
					unsigned int hash = ckey.GetHash();
					Entry* et = m_hashmap.Find(ckey, hash);
					return et ? et->key.rid : -1;
				}
				bool insert(const void* key, int rid)
				{
					if (key == nullptr)return false;
					Entry* et = Alloc(key, rid);
					m_hashmap.Insert(et, et->key.GetHash());

					// 默认负载比例为2.0
					if (m_hashmap.GetCount() > m_hashmap.GetLength()*2.0)
					{
						Expand(m_hashmap.GetCount());
					}
					return true;
				}
				bool remove(const void* key)
				{
					if (key == nullptr)return false;
					ColumnKey ckey;
					ckey.ptr = (const char*)key;
					ckey.bytes = strlen(ckey.ptr);
					ckey.rid = -1;
					unsigned int hash = ckey.GetHash();
					Entry* et = m_hashmap.Remove(ckey, hash);
					if (et)
					{
						m_mem_bytes -= et->key.bytes + 1;
						et->key.Reset();
						m_entry_pool.Free(et);
					}
					return et != NULL;
				}
				void Flush(){}
				void Expand(int capcity, double keybytes = 0)
				{
					int len = m_hashmap.GetLength();
					if (capcity > len)
					{
						int newlength = qb::base::GetHashPrimeLargerThan(capcity);
						m_hashmap.Expand(newlength);
						BLOGINFO("Expand from %d to %d capcity:%d", len, newlength, capcity);
					}
				}
				int GetCount()const{ return m_hashmap.GetCount(); }
			protected:
				Entry* Alloc(const void* key, int rid)
				{
					Entry* et = m_entry_pool.Alloc();
					et->hashnext = et->hashprev = 0;

					int len = strlen((const char*)key);
					m_mem_bytes += len + 1;
					char* ptr = new char[len + 1];
					memcpy(ptr, key, len);
					ptr[len] = 0;
					et->key.ptr = ptr;
					et->key.bytes = len;
					et->key.rid = rid;
					return et;
				}
			};

			class StdHashMap : public std::unordered_map<std::string, int>{
				typedef std::unordered_map<std::string, int> BaseClass;
			public:
				StdHashMap(int capcity, bool useCache) :BaseClass(capcity){}
			};
			class StringIntMap : public std::map<std::string, int>{
			public:
				StringIntMap(int capcity = 0){};
			};
		}
		
		// 将新的容器与std::map<int,int>对比
		class IntIntMap{
			struct Entry{
				int		key;
				int		value;
				Entry() :key(0), value(0){}
				Entry(int k, int v) :key(k), value(v){}
				unsigned int GetHash()const{ return key; }
				void SetValue(int v){ value = v; }
				int GetValue()const{ return value; }
				bool EqualKey(const Entry& et)const{ return key == et.key; }
			};
			LinkedHashMap<Entry, int, F14LinkedChunk<Entry, int>> m_map;
		public:
			void insert(int key, int value)
			{
				m_map.Put(Entry(key, value), value);
			}
			bool find(int key, int& value){
				return m_map.Get(Entry(key, value), value);
			}

		};
		class IntIntVec{
			struct Entry{
				int		key;
				int		value;
				Entry() :key(0), value(0){}
				Entry(int k, int v) :key(k), value(v){}
				unsigned int GetHash()const{ return key; }
				void SetValue(int v){ value = v; }
				int GetValue()const{ return value; }
				bool EqualKey(const Entry& et)const{ return key == et.key; }
				bool operator<(const Entry& et)const{ return key < et.key; }
			};
			std::vector<Entry>	m_items;	// 按照key递增
		public:
			typedef std::vector<Entry>::iterator iterator;
			typedef std::vector<Entry>::const_iterator const_iterator;
			iterator end(){ return m_items.end(); }
			const_iterator end()const{ return m_items.end(); }
			iterator begin(){ return m_items.begin(); }
			void insert(int key, int value)
			{
				insert(key)->value = value;
			}
			iterator insert(int key)
			{
				iterator it = std::lower_bound(m_items.begin(), m_items.end(), Entry(key, 0));
				if (it == m_items.end())
				{
					m_items.push_back(Entry(key, 0));
					return m_items.begin()+m_items.size()-1;
				}
				else{
					if (it->key == key)
						return it;
					else 
						return m_items.insert(it, Entry(key, 0));
				}
			}
			int& operator[](int key){
				return insert(key)->value;
			}
			const_iterator find(int key)const{
				auto it = std::lower_bound(m_items.cbegin(), m_items.cend(), Entry(key, 0));
				if (it != m_items.cend() && it->key == key)
					return it;
				return m_items.cend();
			}
		};

	}//namespace base;
}//namespace ss;